#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

#define BLACK false
#define RED true

template <typename T>
class Node
{
	public:
		T data;
		T high;
		T max;
		Node* lc;
		Node* rc;
		Node* parent;
		bool color;
		Node(T _data, T _high)
		{
			high = _high;
			data = _data;
			max = _high; 
			color = RED;
			parent = lc = rc = NULL;
		}
};

template <typename T>
class IntervalTree
{
	public:
		Node<T>* root;
		Node<T>* nil;
		IntervalTree(T _data, T _high);
		void inorder_walk();
		void inorder_walk(Node<T>* _x);
		Node<T>* min(Node<T>* _x);
		Node<T>* max(Node<T>* _x);
		void insert(T _data, T _high);
		void LeftRotate(Node<T>* _x);
		void RightRotate(Node<T>* _x);
		int transplant(Node<T>* _u, Node<T>* _v);
		Node<T>* search(T _low, T _high);
};

template <typename T>
Node<T>* IntervalTree<T>::search(T _low, T _high)
{
	Node<T>* x = root;
	while (x!=nil && (_low > x->high || _high < x->data))
	{
		if (x->lc != nil && _low <= x->lc->max)
			x = x->lc;
		else
			x = x->rc;
	}
	return x;
}

template <typename T>
int IntervalTree<T>::transplant(Node<T>* _u, Node<T>* _v)
{
    if (_u == nil)
    {
	std::cerr << "Error! Can not transplant to a NULL."<< std::endl;
	std::exit(-1);
    }
    if (_u->parent == nil)
		root = _v;   /// Here can not use _u = _v;
    else if (_u == _u->parent->lc)
		_u->parent->lc = _v;
    else
		_u->parent->rc = _v;
//    if (_v != nil)
    _v->parent = _u->parent;
    return 0;
};

template <typename T>
void IntervalTree<T>::LeftRotate(Node<T>* _x)
{
	T z;
	Node<T>* y = _x->rc;
    _x->rc = y->lc;
    if (y->lc != nil)
		y->lc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
		root = y;
    else if (_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
    y->max = _x->max;
    if (_x->lc == nil && _x->rc != nil)
    {
    	if (_x->high > _x->rc->max)
    		_x->max = _x->high;
    	else
    		_x->max = _x->rc->max;
	}
	else if (_x->rc == nil && _x->lc != nil)
	{
		if (_x->high > _x->lc->max)
    		_x->max = _x->high;
    	else
    		_x->max = _x->lc->max;
	}
    else if (_x->rc != nil && _x->lc != nil)
    {
    	if (_x->lc->max > _x->rc->max)
    		z = _x->lc->max;
    	else
    		z = _x->rc->max;
    	if (z > _x->high)
    		_x->max = z;
    	else
    		_x->max = _x->high;
	}	
};

template <typename T>
void IntervalTree<T>::RightRotate(Node<T>* _x)
{
	T z;
	Node<T>* y = _x->lc;
    _x->lc = y->rc;
    if (y->rc != nil)
		y->rc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
		root = y;
    else if (_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
    y->max = _x->max;
    if (_x->lc == nil && _x->rc != nil)
    {
    	if (_x->high > _x->rc->max)
    		_x->max = _x->high;
    	else
    		_x->max = _x->rc->max;
	}
	else if (_x->rc == nil && _x->lc != nil)
	{
		if (_x->high > _x->lc->max)
    		_x->max = _x->high;
    	else
    		_x->max = _x->lc->max;
	}
    else if (_x->rc != nil && _x->lc != nil)
    {
    	if (_x->lc->max > _x->rc->max)
    		z = _x->lc->max;
   		else
    		z = _x->rc->max;
    	if (z > _x->high)
    		_x->max = z;
    	else
    		_x->max = _x->high;
	}
};

template <typename T>
IntervalTree<T>::IntervalTree(T _data, T _high)
{
	Node<T>* p = new Node<T>(_data, _high);
	nil = NULL;
	root = p;
	root->color = BLACK;
	root->parent = nil;
	root->lc = nil;
	root->rc = nil;
};

template <typename T>
Node<T>* IntervalTree<T>::max(Node<T>* _x)
{
    while (_x->rc != nil)
		_x = _x->rc;
    return _x;
};

template <typename T>
Node<T>* IntervalTree<T>::min(Node<T>* _x)
{
    while (_x->lc != nil)
		_x = _x->lc;
    return _x;
};

template <typename T>
void IntervalTree<T>::inorder_walk()
{
    Node<T>* p = root;
	if (p != nil)
    {
	inorder_walk(p->lc);
	std::cout << p->data << " " << p->color << " " << p->max << "\t\t";
	inorder_walk(p->rc);
    }
};

template <typename T>
void IntervalTree<T>::inorder_walk(Node<T>* _x)
{
	if (_x != nil)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << " " << _x->color << " " << _x->max << "\t\t";
	inorder_walk(_x->rc);
    }
};

template <typename T>
void IntervalTree<T>::insert(T _data, T _high)
{
    Node<T>* x = new Node<T>(_data, _high);
    Node<T>* m = x;
    Node<T>* y = nil;
    Node<T>* z = root;
    while (z != nil)
    {
		y = z;
		if (x->data  < z->data)
	    	z = z->lc;
		else
	    	z = z->rc;
    }
    x->parent = y;
    if (y == nil)
		root = x;
    else if (x->data < y->data)
		y->lc = x;
    else
		y->rc = x;
	x->lc = nil;
	x->rc = nil;
    if (x->parent->color == BLACK)
    	this->root->color = BLACK;
    while (x->parent != this->nil && x->color == RED)
    {
		if (x->parent->color == BLACK)
			break;
		if (x->parent == x->parent->parent->lc)
		{
	    // y is the uncle of x.
	    	Node<T>* y = x->parent->parent->rc;
	    	if (y == nil)
	    	{
	    		if (x == x->parent->rc)
				{
			    	this->LeftRotate(x->parent);
			    	x = x->lc;
				}
				if (x->parent->parent == root)
	    			root = x->parent;
				this->RightRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->rc->color = RED;
				x = x->parent;
				break;
	    	}
	    // case I:
	    	if (y->color == RED)
	    	{
				x->parent->color = y->color = BLACK;
				if (x->parent->parent == root)
					break;
				else
				{
					x->parent->parent->color = RED;
					x = x->parent->parent;
					if (x->parent->color == BLACK)
		    			break;
				}	
	    	}
	    // y->color == BLACK.
	    	else
	    	{
		// tortuous...
				if (x == x->parent->rc)
				{
		    // case II:
		    		this->LeftRotate(x->parent);
		    		x = x->lc;
				}
		// case III:
				this->RightRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->rc->color = RED;
				x = x->parent;
				break;
	    	}
		}
    	else if (x->parent == x->parent->parent->rc)
		{
	    	Node<T>* y = x->parent->parent->lc;
	    	if (y == nil)
	    	{
	    		if (x == x->parent->lc)
				{
			    	this->RightRotate(x->parent);
			    	x = x->rc;
				}
				if (x->parent->parent == root)
	    			root = x->parent;
				this->LeftRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->lc->color = RED;
				x = x->parent;
				break;
	    	}
	    // case I:
	    	if (y->color == RED)
	    	{
				x->parent->color = y->color = BLACK;
				x->parent->parent->color = RED;
				x = x->parent->parent;
				if (x->parent->color == BLACK)
		    		break;
	    	}
	    	else
	    	{
				if (x == x->parent->lc)
				{
		    // case II:
			    	this->RightRotate(x->parent);
			    	x = x->rc;
				}
		// case III:
				this->LeftRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->lc->color = RED;
				x = x->parent;
				break;
	    	}
		}
    	this->root->color = BLACK;
	}
	while ((m->parent != nil) && (m->max > m->parent->max))
	{
		m->parent->max = m->max;
		m = m->parent;
	}
};

int main()
{
	IntervalTree<double> A(8.0, 10.0);
	A.insert(5.0, 7.0);
	A.insert(10.0, 11.0);
	A.insert(6.5, 8.0);
	A.insert(4.0, 11.0);
	A.insert(9.0, 11.0);
	A.insert(11.0, 15.0);
	A.insert(3.0, 7.0);
	A.insert(3.5, 3.6);
	A.inorder_walk();
	std::cout << std::endl;
	std::cout << A.search(4.3, 4.6)->data << "," << A.search(4.3, 4.6)->high << std::endl;
	std::cout << A.search(0.5, 15.5)->data << "," << A.search(0.5, 15.5)->high << std::endl;
	std::cout << A.search(10.5, 11.5)->data << "," << A.search(10.5, 11.5)->high << std::endl;
	return 0; 
} 
